package hot100.logos11To20;

/**
 * @author logos
 * date 2025/7/10 11:52
 * @version v1.0
 * @Package hot100
 */
public class logos12 {

    /**
     * 12. 最小覆盖子串
     * https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public String minWindow(String s, String t) {
            if (s.length() < t.length()) {
                return "";
            }
            char[] sArr = s.toCharArray();
            char[] tArr = t.toCharArray();
            int[] cnt = new int[256];
            for (char c : tArr) {
                cnt[c]--;
            }
            int dept = tArr.length;
            int start = 0;
            int ans = Integer.MAX_VALUE;
            for (int left = 0, right = 0; right < sArr.length; right++) {
                if (cnt[sArr[right]]++ < 0) {
                    dept--;
                }
                if (dept == 0) {
                    while (cnt[sArr[left]] > 0) {
                        cnt[sArr[left++]]--;
                    }
                    if (right - left + 1 < ans) {
                        ans = right - left + 1;
                        start = left;
                    }
                }
            }
            return ans == Integer.MAX_VALUE ? "" : s.substring(start, start + ans);
        }
    }
}
